package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-19
 */

/**
 * 请判断一个链表是否为回文链表。
 */
public class leetcode234 {
    public boolean isPalindrome(ListNode head) {
        if (head==null) return true;
        ListNode firstEnd = findFirstEnd(head);
        ListNode secondHead = findSecondHead(firstEnd.next);

        ListNode p1 = head;
        ListNode p2 = secondHead;
        while (p2!=null){
            if (p1.val!=p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
    //找到链表前半部分的最后一个节点，即中点
    public ListNode findFirstEnd(ListNode root){
        ListNode fast = root;
        ListNode slow = root;
        while (fast.next.next!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //将链表后半部分反转，并返回反转后的首个节点
    public ListNode findSecondHead(ListNode root){
        ListNode pre = null;
        ListNode cur = root;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
